package 查找;

public class interpolationLookups {
    //基本思想：基于二分查找算法，
    // 将查找点的选择改进为自适应选择，可以提高查找效率。
    // 当然，差值查找也属于有序查找。
    public static void main(String[] args) {
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        int number = 0;
        int index = InterpolationLookups(arr,number);
        System.out.println(index);
    }

    private static int InterpolationLookups(int[] arr, int number) {
        int min = 0;
        int max = arr.length - 1;
        while (true) {
            if (min > max) {
                return -1;
            }
            int mdel = min+1/2*(max-min);
            if (arr[mdel] >number) {
                max = mdel - 1;
            } else if (arr[mdel] < number) {
                min = mdel + 1;
            }else {
                return mdel;
            }
        }
    }
}
